package hot100;

import java.util.ArrayList;
import java.util.List;

public class findAnagrams2 {
    public List<Integer> findAnagrams(String s, String p) {
        if(p.length() > s.length()) {
            return new ArrayList<>();
        }

        //双指针+hash表
        int[] hash = new int[127];
        int[] tab = new int[127];
        for(int i = 0;i < p.length();i++) {
            int tem = p.charAt(i) - '0';
            tab[tem]++;
        }
        int total = 0;
        int left = 0;
        int right = 0;
        List<Integer> ret = new ArrayList<>();
        while(right < s.length()) {
            int cur = s.charAt(right) - '0';
            hash[cur]++;
            if(hash[cur] <= tab[cur]) {
                total++;
            }
            if(right - left + 1 > p.length()){
                if(hash[s.charAt(left) - '0'] <= tab[s.charAt(left) - '0']){
                    total--;
                }
                hash[s.charAt(left) - '0']--;
                left++;

            }
            if(total == p.length()) {
                ret.add(left);
            }
            right++;

        }
        return ret;
    }
}
